package com.example.demo.class15_并查集;

/**
 * @program: java_base
 * @description: 岛问题：1的上下左右连城一片，为一岛。
 * @author: zhouhongtao
 * @happyCreateTime: 2022/03/01 13:27
 * // 本题为leetcode原题
 * // 测试链接：https://leetcode.com/problems/number-of-islands/
 * // 所有方法都可以直接通过
 */
public class Code02_NumberOfIslandsDemo {


    public int numIslands(char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        UnionFind unionFind = new UnionFind(grid);

        for (int i = 1; i < col; i++) {
            if (grid[0][i - 1] == '1' && grid[0][i] == '1') {
                unionFind.union(0, i - 1, 0, i);
            }
        }
        for (int i = 1; i < row; i++) {
            if (grid[i - 1][0] == '1' && grid[i][0] == '1') {
                unionFind.union(i - 1, 0, i, 0);
            }
        }
        for (int i = 1;i<row;i++){
            for (int j = 1; j < col; j++) {
                if (grid[i][j] =='1' && grid[i-1][j]=='1'){
                    unionFind.union(i, j, i - 1, j);
                }
                if (grid[i][j] =='1' && grid[i][j-1]=='1'){
                    unionFind.union(i, j, i , j-1);
                }
            }
        }
        return unionFind.sets;
    }

    class UnionFind {
        int[] parents;
        int[] size;
        int[] help;
        int col;
        int sets;

        public UnionFind(char[][] board) {
            col = board[0].length;
            sets = 0;
            int row = board.length;
            int len = row * col;
            parents = new int[len];
            size = new int[len];
            help = new int[len];

            for (int r = 0; r < row; r++) {
                for (int c = 0; c < col; c++) {
                    if (board[r][c] == '1') {
                        int i = getIndex(r, c);
                        parents[i] = i;
                        size[i] = 1;
                        sets++;
                    }
                }
            }
        }


        public void union(int r1, int c1, int r2, int c2) {
            int index1 = getIndex(r1, c1);
            int index2 = getIndex(r2, c2);
            int p1 = find(index1);
            int p2 = find(index2);
            if (p1 != p2) {
                if (size[p1] > size[p2]) {
                    parents[p2] = p1;
                    size[p1] += size[p2];
                } else {
                    parents[p1] = p2;
                    size[p2] += size[p1];
                }
                sets--;
            }
        }

        public int find(int index) {
            int i = 0;
            while (parents[index] != index) {
                help[i++] = parents[index];
                index = parents[index];
            }
            for (i--; i >= 0; i--) {
                parents[help[i]] = index;
            }
            return index;
        }


        // 获取索引
        private int getIndex(int row, int c) {
            return row * col + c;
        }

    }


    /**
     * 感染方式：递归方式
     *
     * @param grid
     * @return
     */
    public int numIslands3(char[][] grid) {
        int islands = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    islands++;
                    infect(grid, i, j);
                }
            }
        }
        return islands;
    }

    // 上下左右 进行感染！ 把char
    //    变成 0 int 型
    private void infect(char[][] grid, int i, int j) {
        // bug代码片段，因为存在i 或者 j < 0 情况。
//        if (i == grid.length  || j == grid[0].length || grid[i][j] != '1') {
//            return;
//        }
        if (i < 0 || j < 0 || i == grid.length || j == grid[0].length || grid[i][j] != '1') {
            return;
        }
        grid[i][j] = 0;
        infect(grid, i + 1, j);
        infect(grid, i - 1, j);
        infect(grid, i, j - 1);
        infect(grid, i, j + 1);
    }


}
